package permutaton;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: javase
 * @description: 全排序, 排序问题不能重复访问当前元素，使用boolean[] isVisited;
 * @author: luolidong
 * @create: 2021-06-13 09:43
 * @version: 1.0
 */
public class Demo {
    boolean[] isVisited;

    public List<List<Integer>> permute(int[] nums) {
        isVisited = new boolean[nums.length];
        List<List<Integer>> list = new ArrayList<>();
        backtrack(list, new ArrayList<>(), nums);
//        backtrack2(list, new ArrayList<>(), nums);
        return list;

    }

    public void backtrack(List<List<Integer>> list, List<Integer> clist,
                          int[] nums) {
        if (clist.size() == nums.length) {
            list.add(new ArrayList<>(clist));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
//            通过判断集合中不能有重复元素
            if (clist.contains(nums[i])) continue;
            clist.add(nums[i]);
            backtrack(list, clist, nums);
            clist.remove(clist.size() - 1);
        }
    }

    public void backtrack2(List<List<Integer>> list, List<Integer> clist,
                           int[] nums) {
        if (clist.size() == nums.length) {
            list.add(new ArrayList<>(clist));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (isVisited[i]) continue;
            isVisited[i] = true;
            clist.add(nums[i]);
            backtrack(list, clist, nums);
            clist.remove(clist.size() - 1);
            isVisited[i] = false;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3};
        List<List<Integer>> permute = new Demo().permute(nums);
        System.out.println(permute);
    }
}
